package solver

import (
	"cmp"
	"log"

	"slices"
)

func compareCells(x, y *Cell) int {
	return cmp.Compare(x.rowNum*9+x.colNum, y.rowNum*9+y.colNum)
}

func equalCells(x, y *Cell) bool {
	return x.rowNum == y.rowNum && x.colNum == y.colNum
}

func shareCells(as, bs []*Cell) []*Cell {
	s := []*Cell{}
	slices.SortFunc(as, compareCells)
	slices.SortFunc(bs, compareCells)
	as = slices.CompactFunc(as, equalCells)
	bs = slices.CompactFunc(bs, equalCells)
	i, j := 0, 0
	for i < len(as) && j < len(bs) {
		switch compareCells(as[i], bs[j]) {
		case 0:
			s = append(s, as[i])
			i++
			j++
		case 1:
			j++
		case -1:
			i++
		}
	}
	return s
}

func (g *Grid) getXYWingCells() (xywBoxes [9][]*Cell, xywRows [9][]*Cell, xywCols [9][]*Cell) {
	for rowNum := 0; rowNum < 9; rowNum++ {
		for colNum := 0; colNum < 9; colNum++ {
			cell := g.cells[rowNum][colNum]
			if cell.candidateCount != 2 {
				continue
			}
			xywBoxes[cell.boxNum] = append(xywBoxes[cell.boxNum], &cell)
			xywRows[cell.rowNum] = append(xywRows[cell.rowNum], &cell)
			xywCols[cell.colNum] = append(xywCols[cell.colNum], &cell)
		}
	}
	return xywBoxes, xywRows, xywCols
}

func candsFromBool(candidates [9]bool) []int {
	vs := []int{}
	for i, candidate := range candidates {
		if candidate {
			vs = append(vs, i)
		}
	}
	return vs
}

func (g *Grid) XYWing() (used bool) {
	xywBoxes, xywRows, xywCols := g.getXYWingCells()
	for _, xywRow := range xywRows {
		for _, xyCell := range xywRow {
			xzCells := findXZ(xywBoxes[xyCell.boxNum], xyCell)
			for _, xzCell := range xzCells {
				if xyCell.rowNum == xzCell.rowNum {
					continue
				}
				xywRow := xywRows[xyCell.rowNum]
				if g.clearupFromYZXZ(xyCell, xzCell, xywRow) {
					used = true
				}

				if xyCell.colNum == xzCell.colNum {
					continue
				}
				xywCol := xywCols[xyCell.colNum]
				if g.clearupFromYZXZ(xyCell, xzCell, xywCol) {
					used = true
				}
			}

			//if xz or yz is in the box of xy, it will repeat.
			xzCells = findXZ(xywRow, xyCell)
			for _, xzCell := range xzCells {
				xywCol := xywCols[xyCell.colNum]
				if g.clearupFromYZXZ(xyCell, xzCell, xywCol) {
					used = true
				}
			}

		}
	}

	return
}

func findXZ(xywHouse []*Cell, xyORzCell *Cell) (xzCells []*Cell) {
	xyORz := candsFromBool(xyORzCell.candidates)
	for _, c := range xywHouse {
		if equalCells(c, xyORzCell) {
			continue
		}
		if c.candidates == xyORzCell.candidates {
			continue
		}
		xz := candsFromBool(c.candidates)

		if len(xyORz) == 3 && slices.Contains(xyORz, xz[0]) && slices.Contains(xyORz, xz[1]) {
			xzCells = append(xzCells, c)
		}
		if len(xyORz) == 2 && (slices.Contains(xyORz, xz[0]) || slices.Contains(xyORz, xz[1])) {
			xzCells = append(xzCells, c)
		}
	}
	return
}

/*
	func getYZ(xyORzCell *Cell, xzCell *Cell) (yz [2]int) {
		xyORz := candsFromBool(xyORzCell.candidates)
		xz := candsFromBool(xzCell.candidates)
		switch {
		case xyORz[0] == xz[0]:
			yz[0], yz[1] = xyORz[1], xz[1]
		case xyORz[0] == xz[1]:
			yz[0], yz[1] = xyORz[1], xz[0]
		case xyORz[1] == xz[0]:
			yz[0], yz[1] = xyORz[0], xz[1]
		case xyORz[1] == xz[1]:
			yz[0], yz[1] = xyORz[0], xz[0]
		}
		if yz[0] > yz[1] {
			yz[0], yz[1] = yz[1], yz[0]
		}
		return
	}
*/
func (g *Grid) clearupFromYZXZ(xyORzCell *Cell, xzCell *Cell, xywHouse []*Cell) (used bool) {
	//yz := getYZ(xyORzCell, xzCell)
	yzCells := findYZ(xywHouse, xyORzCell, xzCell)
	for _, yzCell := range yzCells {
		if g.clearupWing(xyORzCell, xzCell, yzCell) {
			used = true
		}
	}
	return
}

func findYZ(xywHouse []*Cell, xyORzCell *Cell, xzCell *Cell) (yzCells []*Cell) {
	for _, c := range xywHouse {
		if equalCells(c, xyORzCell) || c.boxNum == xyORzCell.boxNum {
			continue
		}
		xyORz := candsFromBool(xyORzCell.candidates)
		xz := candsFromBool(xzCell.candidates)
		yz := candsFromBool(c.candidates)

		//fmt.Println(xyORz, xz, yz)

		//xyz
		if len(xyORz) == 3 && slices.Equal(xyORz, union(xz, yz)) {
			yzCells = append(yzCells, c)
		}
		//xy
		if len(xyORz) == 2 && slices.Equal(yz, symDifference(xyORz, xz)) {
			yzCells = append(yzCells, c)
		}
	}
	return
}

func getZ(xzCell *Cell, yzCell *Cell) (z int) {
	xz := candsFromBool(xzCell.candidates)
	yz := candsFromBool(yzCell.candidates)
	return intersect(xz, yz)[0]
}

func (g *Grid) clearupWing(xyORzCell, xzCell *Cell, yzCell *Cell) (used bool) {
	xzRelCells := []*Cell{}
	xzRelCells = append(xzRelCells, g.boxes[xzCell.boxNum].cells[:]...)
	xzRelCells = append(xzRelCells, g.rows[xzCell.rowNum].cells[:]...)
	xzRelCells = append(xzRelCells, g.cols[xzCell.colNum].cells[:]...)

	yzRelCells := []*Cell{}
	yzRelCells = append(yzRelCells, g.boxes[yzCell.boxNum].cells[:]...)
	yzRelCells = append(yzRelCells, g.rows[yzCell.rowNum].cells[:]...)
	yzRelCells = append(yzRelCells, g.cols[yzCell.colNum].cells[:]...)

	relCells := shareCells(xzRelCells, yzRelCells)
	strategy := "XYWing"

	if xyORzCell.candidateCount == 3 {
		xyzRelCells := []*Cell{}
		xyzRelCells = append(xyzRelCells, g.boxes[xyORzCell.boxNum].cells[:]...)
		xyzRelCells = append(xyzRelCells, g.rows[xyORzCell.rowNum].cells[:]...)
		xyzRelCells = append(xyzRelCells, g.cols[xyORzCell.colNum].cells[:]...)
		relCells = shareCells(relCells, xyzRelCells)
		strategy = "XYZWing"
	}

	z := getZ(xzCell, yzCell)
	for _, cell := range relCells {
		if equalCells(cell, xyORzCell) || equalCells(cell, xzCell) || equalCells(cell, yzCell) {
			continue
		}
		//fmt.Println("relcell", cell.rowNum, cell.colNum)
		if cell.removeCandidate(z + 1) {
			used = true
			//fmt.Println("rm cell", cell.rowNum, cell.colNum)
			log.Printf("(r%vc%v, r%vc%v, r%vc%v) %v %v", xyORzCell.rowNum, xyORzCell.colNum, xzCell.rowNum, xzCell.colNum, yzCell.rowNum, yzCell.colNum, z+1, strategy)
		}
	}
	return
}

func (g *Grid) XYZWing() (used bool) {
	for rowNum := 0; rowNum < 9; rowNum++ {
		for colNum := 0; colNum < 9; colNum++ {
			if g.cells[rowNum][colNum].candidateCount != 3 {
				continue
			}
			if g.XYZWingFromXYZ(&g.cells[rowNum][colNum]) {
				used = true
			}
		}
	}
	return
}

func (g *Grid) XYZWingFromXYZ(xyzCell *Cell) (used bool) {
	xywBoxes, xywRows, xywCols := g.getXYWingCells()
	xzCells := findXZ(xywBoxes[xyzCell.boxNum], xyzCell)
	for _, xzCell := range xzCells {
		if xyzCell.rowNum == xzCell.rowNum {
			continue
		}
		xywRow := xywRows[xyzCell.rowNum]
		if g.clearupFromYZXZ(xyzCell, xzCell, xywRow) {
			used = true
		}

		if xyzCell.colNum == xzCell.colNum {
			continue
		}
		xywCol := xywCols[xyzCell.colNum]
		if g.clearupFromYZXZ(xyzCell, xzCell, xywCol) {
			used = true
		}
	}

	xzCells = findXZ(xywRows[xyzCell.rowNum], xyzCell)
	for _, xzCell := range xzCells {
		if g.clearupFromYZXZ(xyzCell, xzCell, xywCols[xyzCell.colNum]) {
			used = true
		}
	}

	return
}

func (g *Grid) searchBivalueCells() []*Cell {
	cells := []*Cell{}
	for _, row := range g.rows {
		for _, cell := range row.cells {
			if cell.candidateCount != 2 {
				continue
			}
			cells = append(cells, cell)
		}
	}
	return cells
}

func (g *Grid) searchBivaluePairs(bivalueCells []*Cell) [][2]*Cell {
	bivaluePairs := [][2]*Cell{}
	n := len(bivalueCells)
	for i := 0; i < n-1; i++ {
		for j := i + 1; j < n; j++ {
			x := bivalueCells[i]
			y := bivalueCells[j]
			if !slices.Equal(candsFromBool(x.candidates), candsFromBool(y.candidates)) {
				continue
			}
			if x.boxNum == y.boxNum || x.rowNum == y.rowNum || x.colNum == y.colNum {
				continue
			}
			bivaluePairs = append(bivaluePairs, [2]*Cell{x, y})
		}
	}
	return bivaluePairs
}
/*
func searchCandCells(cand int, house *House) []*Cell {
	cells := []*Cell{}
	for _, cell := range house.cells {
		if cell.candidates[cand] {
			cells = append(cells, cell)
		}
	}
	return cells
}

func searchStrongChainsHouse(cand int, house *House) (chain *Chain) {
	cells := searchCandCells(cand, house)
	if len(cells) != 2 {
		return
	}
	chain = &Chain{}
	chain.cand = cand
	chain.cells = [2]*Cell(cells)
	return
}
*/
func findWeakEndsHouse(cand int, baseCell *Cell, house *House) (weakCells []*Cell) {
	for _, cell := range house.cells {
		if cell.solved() || equalCells(baseCell, cell) {
			continue
		}
		if cell.candidates[cand] {
			weakCells = append(weakCells, cell)
		}
	}
	return
}

func (g *Grid) findWeakEnds(cand int, baseCell *Cell) (weakCells []*Cell) {
	weakCells = append(weakCells, findWeakEndsHouse(cand, baseCell, &g.rows[baseCell.rowNum])...)
	weakCells = append(weakCells, findWeakEndsHouse(cand, baseCell, &g.cols[baseCell.colNum])...)
	weakCells = append(weakCells, findWeakEndsHouse(cand, baseCell, &g.boxes[baseCell.boxNum])...)
	return
}

func strongChainHouse(cand int, butNums []int, house *House) bool {
	for cellNum, cell := range house.cells {
		if cell.solved() || slices.Contains(butNums, cellNum) {
			continue
		}
		if cell.candidates[cand] {
			return false
		}
	}
	return true
}

func (g *Grid) strongChain(cand int, cell1, cell2 *Cell) bool {
	if cell1.rowNum == cell2.rowNum {
		if strongChainHouse(cand, []int{cell1.rowNum, cell2.rowNum}, &g.rows[cell1.rowNum]) {
			return true
		}
	}
	if cell1.colNum == cell2.colNum {
		if strongChainHouse(cand, []int{cell1.colNum, cell2.colNum}, &g.cols[cell1.colNum]) {
			return true
		}
	}
	if cell1.boxNum == cell2.boxNum {
		if strongChainHouse(cand, []int{cell1.boxNum, cell2.boxNum}, &g.rows[cell1.boxNum]) {
			return true
		}
	}
	return false
}

func (g *Grid) foundStrongChain(cand int, bivaluePair [2]*Cell) bool {
	endCells1 := g.findWeakEnds(cand, bivaluePair[0])
	endCells2 := g.findWeakEnds(cand, bivaluePair[1])
	for _, cell1 := range endCells1 {
		for _, cell2 := range endCells2 {
			if g.strongChain(cand, cell1, cell2) {
				return true
			}
		}
	}
	return false
}

func (g *Grid) WWing() (used bool) {
	bivalueCells := g.searchBivalueCells()
	bivaluePairs := g.searchBivaluePairs(bivalueCells)
	for _, bivaluePair := range bivaluePairs {
		cands := candsFromBool(bivaluePair[0].candidates)
		for i, cand := range cands {
			if !g.foundStrongChain(cand, bivaluePair) {
				continue
			}
			if g.clearupSkycraper(cands[1-i], bivaluePair[:]) {
				used = true
			}
		}
	}
	return
}
